package twobranchTree.preorderTraversal;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * @Date 2020/2/9
 * @author 王光浩
 * @Description 给出一个二叉树，使用前序遍历这个二叉树。
 * @Thinking 使用迭代方法。使用队列+栈来实现迭代
 *           复杂度分析：时间复杂度O（n），空间复杂度O（2n）
 *           但是在提交后为什么运行时间比较长：第一个原因是这题本来使用栈就可以实现的，但是自己使用栈+队列；第二个原因
 *                                           是Stack继承了Vector，内部使用的是动态数组，所以可能会存在扩容问题，因此以后
 *                                           使用Stack最好使用LinkedList（内部使用了双向链表——比Stack更高效）
 */
public class MyMethodTwo {
	public List<Integer> preorderTraversal(TreeNode root) {
		Queue<TreeNode> queue=new LinkedList<TreeNode>();  //实现先进先出，保存左子树
		Stack<TreeNode> stack=new Stack();          //实现后进先出，保存右子树
		List<Integer> result=new ArrayList<Integer>();
		if(root!=null)queue.add(root);
		TreeNode top=null;
		//迭代实现前序遍历
		while(!queue.isEmpty() || !stack.isEmpty()) {
			if(!queue.isEmpty())top=queue.poll();
			else top=stack.pop();
			result.add(top.val);
			if(top.left!=null)queue.add(top.left);
			if(top.right!=null)stack.add(top.right);
		}
		return result;
	}
	/**
	 * 利用 栈结构 的先进后出的特性来对二叉树进行前序遍历
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> ret = new ArrayList<Integer>();
		if (root == null)
			return ret;
		//不使用 Stack 是因为 Stack 可以在任意地方插入数据（继承 Vector）
		Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
		stack.add(root);
		//前序遍历二叉树，将遍历的结果存放到 List 集合中
		while ( !stack.isEmpty() ) {
			TreeNode node = stack.pollLast();
			ret.add(node.val);
			if (node.right != null)
				stack.add(node.right);
			if (node.left != null)
				stack.add(node.left);
		}
		return ret;
	}
}
